package daily.year2024.m11;

import java.util.ArrayList;
import java.util.List;

/**
 * No.658 找到k个最接近的元素
 *
 * @author wjs 2024/11/11
 */
public class d11 {
    class Solution {
        //滑动窗口
        //维护一个长度为k的滑动窗口，计算窗口内与x差值绝对值的和，取最小值的区间
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            int n = arr.length;
            int l = 0, r = 0;
            int s = 0, e = 0;
            int sum = 0, min = 2147483647;
            while(r < k) {
                sum += Math.abs(arr[r] - x);
                r++;
            }
            if(min > sum) {
                min = sum;
                s = l;
                e = r;
            }
            while(r < n) {
                sum -= Math.abs(arr[l] - x);
                l++;
                sum += Math.abs(arr[r] - x);
                r++;
                if(min > sum) {
                    min = sum;
                    s = l;
                    e = r;
                }
            }
            List<Integer> list = new ArrayList<>();
            for(int i=s;i < e;i++) {
                list.add(arr[i]);
            }
            return list;
        }
    }
}
